\documentclass[a4paper,UTF8,noindent,10pt]{ctexart}

\usepackage {graphicx}
\usepackage {paralist}
\usepackage {marginnote}
\usepackage {amsmath}
\usepackage {tikz}
\CTEXsetup[format={\Large\bfseries}]{section}

\pagestyle{plain}

\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=c,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=right,
  numberstyle=\small\color{green},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=4, 
  escapeinside=``
}

\begin {document}

\section{题目}
\subsection{描述}
给出一个长度不超过200的由小写英文字母组成的字母串(约定: 该字串以每行20个字母的方式输入，
且保证每行一定为20个)。要求将此字母串分成k份$(1<k \leq 40)$，且每份中包含的单词个数加起来总数
最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串
this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。
\subsection{输入}
每组的第一行有2个正整数(p,k)

p表示字串的行数,k表示分为k个部分。

接下来的p行，每行均有20个字符。

再接下来有1个正整数s，表示字典中单词个数。(1≤s≤6)

接下来的s行，每行均有1个单词。

\subsection{输出}
1个整数，分别对应每组测试数据的相应结果。

\subsection{输入样例1}
\begin{lstlisting}
1 3
thisisabookyouareaoh
4
is
a
ok
sab
\end{lstlisting}
\subsection{输出样例1}
\begin{lstlisting}
7
\end{lstlisting}

\subsection{提示说明}
\begin{lstlisting}
this/isabookyoua/reaoh
\end{lstlisting}

\section{思路分析}
本题分为两步：（1）先求出$w[i][j]$，从i到j的单词数量；(2)求出$F[i][j]$，从0开始到第i个字符，分为j份，所包含单词的最大数量。
\par
先把单词按照长短进行排序，短的排到前面。然后一次查找a[i]开始是否为某个单词的起始位置。如果是，则把$w[x][y]$ 加一, 其中$1 \leq x \leq i, i+wlen \leq y \leq 20\cdot p$
\par
求$F[i][j]$的方法为DP，状态转移方程为$F[i][j] = max(F[r][j-1]+w[r+1][i]) , r=j...i-1$，初始化$F[i][1] = w[1][i]$。

\section{代码实现}
\begin{lstlisting}
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; 
#define MAX_N	201
#define INF		100000
int p, k, s; 
char a[MAX_N]; 
int alen; 
struct word_s {
	char w[MAX_N]; 
	int len; 
}; 
struct word_s word[10]; 
int w[MAX_N][MAX_N]; 
int F[MAX_N][MAX_N]; 

bool cmp(word_s &a, word_s &b)
{
	return a.len<b.len; 
}

int main()
{
	int i, j, r; 
	int x, y; 

	freopen("p1026_03.in", "r", stdin); 
	scanf("%d %d\n", &p, &k); 
	for(i=0; i<p; i++) {
		scanf("%s\n", a+20*i+1); 
		*(a+20*i+20+1)='\0'; 
	}
	alen = p*20; 
	scanf("%d\n", &s); 
	for (i=0; i<s; i++) {
		scanf("%s", word[i].w); 
		word[i].len = strlen(word[i].w);
	}
	sort(word, word+s, cmp); 

	for (i=1; i<=alen; i++) {
		for (j=0; j<s; j++) {
			if (strncmp(a+i, word[j].w, word[j].len)!=0) {
				continue;
			}
			for (x=1; x<=i; x++) {
				for (y=i+word[j].len-1; y<=alen; y++) {
					w[x][y] ++; 
				}
			}
			break; 
		}
	}
	for (i=1; i<=alen; i++) {
		F[i][1] = w[1][i]; 
	}
	// F[i][j] = max(F[r][j-1]+w[r+1][i]) , r=j...i-1
	for (i=1; i<=alen; i++) {
		for(j=1; j<=k; j++) {
			F[i][j] = max(0, F[i][j]); 
			for (r=j; r<=i-1; r++) {
				F[i][j] = max(F[i][j], F[r][j-1]+w[r+1][i]); 
			}
		}
	}	
	printf("%d\n", F[alen][k]); 
	return 0; 
}


\end{lstlisting}


\end {document}








